Heuristic Optimization for Decentralized Frequent Itemset Counting.

Probabilistic Data Consistency for Wide%2DArea Applications.

Frequent Itemset Counting Across Multiple Tables.

Data Organization and Access for Efficient Data Mining.
Efficient mining of data presents a significant challenge due to problems of combinatorial explosion in the space and time often required for such processing. While previous work has focused on improving the efficiency of the mining algorithms, we consider how the representation, organization, and access of the data may significantly affect performance, especially when I/O costs are also considered. By a simple analysis and comparison of the counting stage for the Apriori association rules algorithm, we show that a &#034;column-wise&#034; approach to data access is often more efficient than the standard row-wise approach. We also provide the results of empirical simulations to validate our analysis. The key idea in our approach is that counting in the Apriori algorithm with data accessed in a column-wise manner significantly reduces the number of disk accesses required to identify itemsets with a minimum support in the database --- primarily by reducing the degree to which data and counters need...
A piggyback method to collect statistics for query optimization in database management systems.
A database management system (DBMS) usually performs query optimization based on statistical information about data in the underlying database. Out-of-date statistics may lead to inefficient query processing in the system. Existing solutions to this problem have some drawbacks such as heavy administrative burden, high system load, and tardy updates. To overcome these drawbacks, our new approach, called the piggyback method, is proposed in this paper. The key idea is to piggyback some additional retrievals during the processing of a user query in order to collect more up-to-date statistics. The collected statistics are used to optimize the processing of subsequent queries. To specify the piggybacked queries, basic piggybacking operators are defined in this paper. Using the operators, several types of piggybacking such as vertical, horizontal, mixed vertical and horizontal, and multi-query piggybacking are introduced. Statistics that can be obtained from different access methods...
Characterizing Multicast Orderings Using Concurrency Control Theory.
Coordinating distributed executions is achieved by two widely used approaches: process groups and transactions. Typically, the two represent a trade-off in terms of the degrees of consistency and performance. By applying transaction concurrency control techniques to characterize and design process group multicast orderings, we aim to provide aspects of both ends of the trade-off. In particular, we propose a framework in which each message multicast is regarded as a transaction. Appropriate message ordering protocols are devised and shown to be correct using a variant of concurrency control theory. Also, we are able to incorporate certain aspects of application semantics for which existing process group approaches are inadequate. Finally, our framework provides a means to characterize the performance of orderings to allow a comparison of different ordering protocols. 1 Introduction  Distributed applications typically require that the largely autonomous executions at the separate sites b...
Customized metadata for Internet information.

Logic%2Denhanced memory for high performance databases.

Real%2DTime Data and Coordination Control for Reconfigurable Manufacturing Systems.

Towards Distributed Real%2DTime Concurrency and Coordination Control.

Formalizing Database Recovery.
Abstract: Failure resilience is an essential requirement for database systems, yet there has been little e ort to specify and verify techniques for failure recovery formally. The desire to improve performance has resulted in algorithms of considerable sophistication, yet understood by few and prone to errors. In this paper, we illustrate how the methodology of Gurevich Abstract State Machines can elucidate recovery and provide formal rigor to the design of a recovery algorithm. In a series of re nements, we model a recovery algorithm at several levels of abstraction, verifying the correctness of each model. This work suggests that our approach can be applied to more advanced recovery mechanisms.
Report on DART %2796 Databases Active and Real%2DTime %28Concepts meet Practice%29.

Report on DART %2796 Databases Active and Real%2DTime %28Concepts meet Practice%29.

Performance aspects of dynamic re%2Dallocation for partitioned data.

Employing Logic%2DEnhanced Memory for High%2DPerformance ATM Network Interfaces.

Probabilistic Real%2DTime Data Access with Interval Constraints.
Real-time data management for manufacturing control applications indicates a need for probabilistic deadline guarantees and interval constraints. When shared data objects are treated as resources, real-time data management becomes a resourceconstrained real-time scheduling problem. In this paper, we perform simulations and measurements to evaluate the utilities of existing real-time scheduling algorithms in our University of Michigan Open-Architecture Controller testbed environment. We exhibit that, among rate-monotonic, first-infirst -out and earliest-deadline-first, none can consistently outperform the others in terms of miss ratio. To satisfy interval constraints in the presence of timer interval variance and &#034;memory,&#034; resetting timers is intuitively helpful. However, we find that it is not a viable approach even when the associated overhead is negligible. Rate-monotonic and first-in-first-out perform well in simulations, but the real-time operating system (QNX) has significant unpredictability---thus the performance is not as satisfactory in the testbed. To our knowledge, this research is the first empirical studies of real-time scheduling algorithms in the context of probabilistic deadline guarantees and interval constraints.
Logic%2DEnhanced Memory Database A Simulation Study.

Run%2DTime Parallelization of Sequential Database Programs.

Formalizing Recovery in Transaction%2DOriented Database Systems.

Databases with Deadline and Contingency Constraints.
Real-time database systems associate the concept of deadlines with transaction executions. Previous approaches use &#034;best effort&#034; techniques to schedule a given set of transactions to meet the deadlines as well as to ensure the consistency of the database. However, such approaches are inadequate for target applications which have &#034;hard&#034; real-time deadlines that need to be met in the event of crisis situations. In such cases, it is important to obtain contingency plans that may be invoked with guaranteed execution time characteristics. This paper presents an alternative model for real-time database systems in which deadlines are associated with &#034;contingency&#034; constraints rather than directly with transactions. Our approach leads to a predicatebased model that intrinsically incorporates both triggering and relative timing constraints regarding the transaction executions. We exhibit that selecting contingency plans with respect to various optimality criteria has inherent computational ineff...
Adaptive Commitment for Distributed Real%2DTime Transactions.


Failure%2DResilient Transaction Management in Multidatabases.
The ensuring of correct transaction executions in practical multidatabase systems is a difficult problem, since few changes are permissible in the constituent local database systems to accommodate the demands of the distributed environment. In this paper, we show that the preservation of two aspects of local autonomy --- the degrees of control over the transactions by the sites (execution autonomy), and the multidatabase system (control autonomy) --- has implications with regard to the correct executions of transactions in a multidatabase system that is susceptible to failures. The relationship between the local autonomy and achieving correct executions sheds some light on the reasons behind some of the difficulties that have been encountered in previous research. We show that for transaction management in multidatabases, certain trade-offs must be made in order to achieve correct executions despite the possibility of failures. We examine several of the previously proposed approaches i...



On the Interconnection Constants of Hopfield Nets.

